This invention relates to computer networks, and more particularly to prevention of unauthorized access to a local network from computers external to the local network.
Prevention of unauthorized access by outsiders to a computer network is a part of any network management program. This security problem has been complicated by recent trends in internetworking of a previously isolated private networks with value added networks, public networks (such as the internet), and with the networks of other enterprises.
Firewalls are one approach to preventing unauthorized access. Essentially, a firewall is a control layer inserted between an enterprise""s network and the outside. It permits only some traffic to pass through. The firewall is configured by the administrator of the local network based on the enterprise""s security policy. For example, the firewall may block traffic of a certain type, traffic from certain addresses, or traffic from all but a predetermined set of addresses.
Techniques used by network intruders for penetrating network system security have evolved in pace with sophisticated methods for detecting the intruders. Detection methods include software solutions, specifically, software intrusion detection systems, which continually monitor network traffic and look for known patterns of attack.
When an intrusion detection system detects inappropriate activity, it generates appropriate alarms and provides other responses while the attack is occurring. For example, the intrusion detection system might report the attack, log the attack, and terminate the misused connection.
One approach to intrusion detection relies on known patterns of unauthorized activity, referred to as xe2x80x9csignaturesxe2x80x9d. These signatures are stored, and, in real time, compared to the packet flow incoming to the network. If a match is found, the incoming datastream is assumed to be misused.
Many existing intrusion detection systems are host-based rather than network based. A host-based system resides on a particular host computer and detects only attacks to that host. A host-based system is described in U.S. Pat. No. 5,557,742, entitled xe2x80x9cMethod and System for Detecting Intrusion and Misuse of a Data Processing Systemxe2x80x9d.
A network-based system is connected at some point on a local network and detects attacks across the entire local network.
As an example of network-based intrusion detection, one known pattern of unauthorized access is associated with xe2x80x9cIP spoofingxe2x80x9d, whereby an intruder sends messages to a computer with an IP address indicating that the message is from a trusted port. To engage in IP spoofing, the intruder must first use a variety of techniques to find an IP address of a trusted port and must then modify the packet headers so that it appears that the packets are coming from that port. This activity results in a signature that can be detected when matched to a previously stored signature of the same activity.
For signatures indicated by a single packet, the detection process can be as simple as matching a binary string of an incoming packet to a stored binary string. However, for composite signatures, the detection process often requires the use of procedural code, involving loops, counts, comparisons and other processing mechanisms. For this reason, conventional signature detection methods require a skilled programmer to write the signatures.
Once signatures are defined, some sort of signature analysis engine must be developed to compare incoming data to a stored collection of known reference signatures. Various pattern matching techniques are possible, as are various techniques for structuring the stored reference signatures so as to facilitate the matching process.
One aspect of the invention is a method of using a decision graph to detect signatures representing misuse of a local network. A set of known signatures having one or more common events are identified, and represented with a decision graph having a node for each common event. From the common node, the graph may branch to lower level nodes, each lower level node representing an event associated with only one (or some) of the signatures. Leaf nodes represent the bottom of a path of events that comprise a signature. The path down the decision graph depends on the outcome of xe2x80x9ctestxe2x80x9d functions associated with each node other than leaf nodes. The decision graph permits a search for multiple signatures with only one traversal of the decision graph, and avoids the need for a separate matching process for each signature.
As a very simple example of a decision graph, two different signatures might have the same parent node. The parent node might then have two test functions, the outcome of which cause a branch into separate paths. Each path represents a sequence of events unique to each signature.
An advantage of the invention is that an entire set of reference signatures can be consolidated into a smaller set of decision graphs. The use of a single decision graph for multiple signatures results in more efficient processing. Signatures having common events can be identified, and decision graphs optimized so that they represent those signatures that are most efficiently processed together. Each common event in a decision graph results in one matching step for that event rather than one matching step for each signature. Depending on the number of common events that are processed together, the overall reduction in the processing load can be substantial.